package com.cy.letcode.递归;

import java.util.*;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * <p>
 * 示例：
 * <p>
 * 输入：n = 3
 * 输出：[
 * "((()))",
 * "(()())",
 * "(())()",
 * "()(())",
 * "()()()"
 * ]
 * n=2时
 * (())
 * ()()
 * <p>
 * n=1时
 * ()
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/generate-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {

    public static void main(String[] args) {
        List<String> strings = generateParenthesis(20);
        System.out.println(strings.size());
        for (String string : strings) {
            System.out.println(string);
        }
    }

    public static List<String> generateParenthesis(int n) {
        String str = "()";
        Set<String> set = new HashSet<>();
        Set<String> newSet = new HashSet<>();
        set.add(str);
        for (int i = 1; i < n; i++) {
            for (String s : set) {
                newSet.add("(" + s + ")");
                newSet.add("()" + s);
                newSet.add(s + "()");
            }
            if (i % 2 == 1 && i != 1) {
                str = "(" + str + ")";
                newSet.add(str + str);
            }
            set.clear();
            set.addAll(newSet);
            newSet.clear();
        }
        return new ArrayList<>(set);

    }

}